package com.salim.leetcode.$94;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BinaryTreeInorderTraversal {
    //树的中序遍历 左 根 右 要求使用迭代
    //先一直入栈左
    //如果碰到节点左右都没有 回退一个 即pop之后取栈顶 并把pop出的元素加入结果
    //这时左边已经走过了 开始走右边
    // push右节点进去 继续入栈左

    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current;
        List<Integer> result = new ArrayList<>();
        if(root==null){
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            current = stack.peek();
            if(current.left!=null){
                stack.push(current.left);
            }else if(current.right!=null){
                stack.pop();
                result.add(current.val);
                stack.push(current.right);
            }else{
                stack.pop();
                result.add(current.val);
                if(!stack.isEmpty()){
                    stack.peek().left = null;
                }
            }
        }
        return result;
    }



    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
